package 剑指offer;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-13
 */
public class 编辑距离 {
    //当做备忘录
    static class Visit {
        int val;
        boolean visited = false;
    }

    static Visit[][] memo = new Visit[10][10];

    static {
        for (int i = 0; i < memo.length; i++) {
            for (int j = 0; j < memo[0].length; j++) {
                memo[i][j] = new Visit();
            }
        }
    }

    //添加备忘录，减少重叠子问题
    static int minDistanceMemo(String str1, String str2, int i, int j) {
        if (i == -1) {
            return j + 1;
        }
        if (j == -1) {
            return i + 1;
        }
        if (memo[i][j].visited) {
            return memo[i][j].val;
        }
        if (str1.charAt(i) == str2.charAt(j)) {
            memo[i][j].val = minDistanceMemo(str1, str2, i - 1, j - 1);
            memo[i][j].visited = true;
            return memo[i][j].val;
        } else {
            memo[i][j].val = Math.min(Math.min(
                    minDistanceMemo(str1, str2, i, j - 1) + 1,  //插入
                    minDistanceMemo(str1, str2, i - 1, j) + 1), //删除
                    minDistanceMemo(str1, str2, i - 1, j - 1) + 1); //替换
            memo[i][j].visited = true;
            return memo[i][j].val;
        }
    }
    //DP减少重复子问题

    static int minDistanceDP(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= n; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
